高考申論題
109年
[資訊處理] 資料結構
第 二 題
📖 題組：
三、請回答下列關於AVL樹（AVL Tree）的問題：
三、請回答下列關於AVL樹（AVL Tree）的問題：
請提供一個線性時間的演算法來判斷一個二元搜尋樹是否為AVL樹。（10分）
📝 此題為申論題
思路引導 VIP
題目已保證是 BST，所以只要確認「平衡條件」即可。AVL 的平衡條件是任意節點的左右子樹高度差絕對值 ≤ 1。為了達到 O(n) 的線性時間，必須使用後序追蹤 (Post-order) 的概念：先問左右子樹是否為 AVL，順便拿到左右子樹的高度，算出目前節點高度並檢查高度差，避免重複計算高度。
🤖
AI 詳解
AI 專屬家教
【考點分析】 AVL 樹平衡定義、樹的後序追蹤（Post-order Traversal）、遞迴演算法設計。 【理論/法規依據】
▼ 還有更多解析內容